// https://www.lintcode.com/problem/kth-largest-element/description

// 分治法解决两个排序数组中的第k大
// https://gitee.com/xuzh1874/OJ/blob/master/Basis/Algorithm/%E5%88%86%E6%B2%BB/median-of-two-sorted-arrays.cpp

class Solution {
public:
    /**
     * @param n: An integer
     * @param nums: An array
     * @return: the Kth largest element
     */
class Solution {
public:
    /**
     * @param n: An integer
     * @param nums: An array
     * @return: the Kth largest element
     */
    int partion (vector<int> &nums, int start, int end, int k)
    {
        int low = start;
        int high = end;
        int mid = (high - low) / 2 + low;
        int p = nums[mid];
        while (low < high)
        {
            while (nums[low] > p) low++; //注意是倒着排序
            while (nums[high] < p) high--;
            if (low <= high)
            {
                swap(nums[low], nums[high]);
                low++;
                high--;
            }
        }
        if (k >= low && low < end) partion(nums, low, end, k); //注意判断low < end.注意不包含=，会报错
        if (k <= high && high > start) partion(nums, start, high, k);
        return nums[k];
    }
    int kthLargestElement(int n, vector<int> &nums) {
        return partion(nums, 0, nums.size() - 1, n - 1); //注意是n-1
    }
};

    int kthLargestElement(int n, vector<int> &nums) {
        return partition(nums, 0, nums.size() - 1, n - 1);
    }
};